#include <assert.h>
#include <stdlib.h>
#include <stdio.h>

#include "bittreeiter.h"
#define     DEADBEAF            ((void*)0xdeadbeef)

typedef struct bitsubtr_t
{
    void*                   m_data;
    struct bitsubtr_t*      m_parnt;
    struct bitsubtr_t*      m_small;
    struct bitsubtr_t*      m_big;
} subtr;

struct BitTree_t
{
    Less        m_lessF;
    subtr       m_End;/*Like End stub in STL , usefull to find Last element at O(1)*/
    subtr*      m_root;
    subtr*      m_Begin;/*Pointer ot minimal element in Tree*/
};

/********************service funciton ***********************************************************************/
 /*returns subtr* to insert data*/

 static void    TreeEmptyTreeInitiallizing(Tree* _this);
 static subtr*  TreeInsertSubtr(subtr* _End, subtr* _root, subtr* newnode, Less m_lessF);
 static void    TreeUpdateEndBegin(Tree* _this,subtr* _data);
 static subtr*  TreeFindSubtr(subtr* _End, subtr* _root, void* _data,Less _less);
 static subtr*  TreeFindMinOnLeaf(subtr* _node);
 static subtr*  TreeFindMaxOnLeaf(subtr* _node);
 static void    TreeReplaceLinks(Tree* _this,subtr* _newnod,subtr* _oldnod);
 static void    ReplaceLinkOnBigSide(Tree* _this,subtr* _newnod,subtr* _oldnod);
 static  void   ReplaceLinkOnSmallSide(Tree* _this,subtr* _newnod,subtr* _oldnod);
 static int     TreeRemoveIfNoChilds(Tree* _this, TreeIter _iter);

 typedef int (*TreeWorkFunc) (void*,void* _state);
 static void TreeFor_Each(Tree* _tree,TreeWorkFunc _func,void* _state);

 static void    TreeFor_EachItself(subtr* _End, subtr* _node,TreeWorkFunc _func,void* _state);
 static void    TreeInvalidateNode(subtr* node);
 static TreeIter  TreeFindNodeForReplace(Tree* _this, TreeIter _iter);
 int            TreeDeleteNode(void* _node,void* _state);



/*****************************************************************************************/
 Tree* TreeNew(Less _less)
 {
     Tree*       tree;
     assert(_less);

     if (0 == (tree = (Tree*) malloc(sizeof(Tree))))
     {
         fprintf(stderr,"\n TREE ALLOCATION FAILED , LINE %d \n", __LINE__);
         return 0;
     }


     TreeEmptyTreeInitiallizing(tree);/*Begin,root and End.parn initiallizing*/

     tree->m_lessF = _less;
     tree->m_End.m_data  = DEADBEAF;
     tree->m_End.m_small = 0;/*Don't chagne it to DEADBEAF it uses in Next and Prev"*/
     tree->m_End.m_big   = 0;/*Don't chagne it to DEADBEAF it uses in Next and Prev"*/
     return tree;
 }

 TreeIter TreeInsert(Tree* _this,void* _data)
 {
     subtr*         newnode=0;
     assert(_this);
     assert(_data);

    if (0 == (newnode = (subtr*) malloc(sizeof(subtr))))
     {
         fprintf(stderr,"\n NODE ALLOCATION FAILED , LINE %d \n", __LINE__);
         return (TreeIter)&_this->m_End;
     }

     /*Filling the newnode*/
     newnode->m_data  = _data;
     newnode->m_parnt = 0;
     newnode->m_small = 0;
     newnode->m_big   = 0;

     _this->m_root=TreeInsertSubtr(&_this->m_End, _this->m_root,newnode,_this->m_lessF);
    TreeUpdateEndBegin(_this,newnode);
    return (TreeIter)newnode;
 }

 TreeIter TreeFind(Tree* _this,void* _data)
 {
     assert(_this);
     assert(_data);
     return (TreeIter)TreeFindSubtr(&(_this->m_End), _this->m_root,_data,_this->m_lessF);
 }

int TreeIsEmpty(Tree* _this)
{
    assert(_this);
    return _this->m_root == &(_this->m_End);
}

int   TreeIsEqual(TreeIter _iter1,TreeIter _iter2)
{
    assert(_iter1);
    assert(_iter2);
    return _iter1 == _iter2;
}

void* TreeGetData(TreeIter _iter)
{
    assert(_iter);
    return ((subtr*) _iter)->m_data;
}

TreeIter  TreeEnd(Tree* _this)
{
    assert(_this);
    return (TreeIter)&_this->m_End;
}

TreeIter  TreeBegin(Tree* _this)
{
    assert(_this);
    return (TreeIter)(_this->m_Begin);
}

TreeIter  TreeNext(TreeIter _iter)
{
    subtr*      node=(subtr*)_iter;

    assert(_iter);

    /*find is the next exsist on "big" branch below node*/
    if(node->m_big != 0)
    {
        return (TreeIter)TreeFindMinOnLeaf(node->m_big);
    }

    /*Goes to up levels in tree. The stop codition is parent is bigger than node*/
    while(node->m_parnt->m_small != node)
    {
        node=node->m_parnt;
    }

    node=node->m_parnt;

    return (TreeIter)node;
}

TreeIter  TreePrev(TreeIter _iter)
{
    subtr*      node=(subtr*)_iter;

    assert(_iter);

    /*find is the previous exsists on branch below node*/
    if(node->m_small != 0 )
    {
        return (TreeIter)TreeFindMaxOnLeaf(node->m_small);
    }

    /*Goes to up levels in tree. The stop codition is parent is less than node*/
    while(node->m_parnt->m_big != node)
    {
        node=node->m_parnt;
    }
    node=node->m_parnt;

    return (TreeIter)node;
}

TreeIter  TreeRemoveNode(Tree* _this, TreeIter _iter)
{
    TreeIter      itr_repl;
    subtr*        parnt;
#ifdef unitest_bittree_local
    subtr*      Nnode;
    long*        Ndata;
    subtr*      Tnode;
    long*       Tdata;
    subtr*      Rnode;
    long*      Rdata;
#endif /*unitest_bittree_local*/

    assert(_iter);
    assert(_this);

     /*cheks is the Tree  empty*/
     /*cheks is sended itr non legal as End*/
     /*To check is the _iter relates to existed element
     the funciton TreeFind coud be used instead but it will reduce the performace of remove*/
     if (TreeIsEmpty(_this) && (subtr*)_iter == &_this->m_End )
     {
         return (TreeIter)&_this->m_End;
     }

#ifdef unitest_bittree_local_
    Nnode = (subtr*)next_iter;
    Ndata = (long*)Nnode->m_data;
    Tnode = (subtr*)_iter;
    Tdata = (long*)Tnode->m_data;
#endif /*unitest_bittree_local*/

    parnt=((subtr*)_iter)->m_parnt;
    /*remove  nodes without children (also Begin and Last Valid without children and root)*/
    if (TreeRemoveIfNoChilds(_this,_iter))
    {
        return (TreeIter) parnt;
    }

    /*Returns _iterator to node wich will replace the _iter :
     minimal from big side or maximal from small side
    ONLY on brachnes below the _iter*/
     itr_repl = TreeFindNodeForReplace(_this,_iter);
#ifdef unitest_bittree_local
    Rnode = (subtr*)itr_repl;
    Rdata = (long*)Rnode->m_data;
#endif /*unitest_bittree_local*/

     /*remove  nodes with childer*/
     TreeReplaceLinks(_this,(subtr*)itr_repl,(subtr*)_iter);
     return itr_repl;
}



void  TreeDeleteTree(Tree* _tree)
{
    TreeFor_Each(_tree,TreeDeleteNode,0);
    free(_tree);
    return;
}

/****************************Local function implementation***********************/

int  TreeDeleteNode(void* _node,void* _state)
{
    free(_node);
    return 0;
}

/* Function operates in "In Order" sequence. Third argument is some variable
 to store the "TreeWorkFun"  state.
 If function "TreeWorkFun" is statless,0 can be provided.*/
void TreeFor_Each(Tree* _tree,TreeWorkFunc _func,void* _state)
{
    TreeFor_EachItself(&_tree->m_End,_tree->m_root,_func,_state);
    return;
}

static void TreeFor_EachItself(subtr* _End, subtr* _node,TreeWorkFunc _func,void* _state)
{
     if(_node == 0 || _node== _End)
     {
         return;
     }
     TreeFor_EachItself(_End,_node->m_small, _func,_state);
     _func(_node->m_data,_state);
      TreeFor_EachItself(_End,_node->m_big, _func,_state);
    return;
 }

/*returns 1 if node was removed and 0 if not (to satisfied to removed criterias*/
static int TreeRemoveIfNoChilds(Tree* _this, TreeIter _iter)
{
     subtr*      node=(subtr*)_iter;

    /*The removed not is Not End or Begin and it has no childs*/
    if(!node->m_small && !node->m_big )
    {
        if(node->m_parnt->m_small == node)
        {
            node->m_parnt->m_small = 0;
        }
        else
        {
            node->m_parnt->m_big = 0;
        }
        TreeInvalidateNode(node);
        free(node);
        return 1;
    }

    /*if it is Begin and it is not the root and has no childs
    (this is condition that it is not root: && node != _this->m_root  also included to second condition*/
    if(node->m_small == &_this->m_End && !node->m_big)
    {
        _this->m_Begin = node->m_parnt;
        node->m_parnt->m_small = &_this->m_End;
#ifdef unitest_bittree_local
        TreeInvalidateNode(node);
#endif /*unitest_bittree_local*/
        free(node);
        return 1;
    }

       /*if it is Last Valid and it is not the root*
       (this is condition that it is not root: && node != _this->m_root  also included to second condition*/
    if(node->m_big == &_this->m_End  && !node->m_small )
    {
        _this->m_End.m_parnt = node->m_parnt;
        node->m_parnt->m_big = &_this->m_End;
        free(node);
        TreeInvalidateNode(node);
        return 1;
    }

    /*if it is root and has no childer *
    (this is condition that it is the root: && node == _this->m_root also included to second condition*/
     if(_this->m_Begin == node && node->m_big == &_this->m_End )
     {
         TreeEmptyTreeInitiallizing(_this);

#ifdef unitest_bittree_local
          TreeInvalidateNode(node);
#endif /*_unitest_bittree_local*/
          free(node);
         return 1;
     }
     return 0;
}
static void TreeEmptyTreeInitiallizing(Tree* _this)
{
    _this->m_root  =&(_this->m_End);
    _this->m_Begin = &(_this->m_End);
    _this->m_End.m_parnt = &(_this->m_End);
}

static void TreeInvalidateNode(subtr* _node)
{
     _node->m_data  = DEADBEAF;
     _node->m_parnt = DEADBEAF;
     _node->m_small = DEADBEAF;
     _node->m_big   = DEADBEAF;
}

static void TreeReplaceLinks(Tree* _this,subtr* _newnod,subtr* _oldnod)
{
    /*determined the parent of oldnod and connect it to newnod and werswise*/
    if(_this->m_root != _oldnod  && _oldnod->m_parnt->m_big ==  _oldnod)
    {
        _oldnod->m_parnt->m_big = _newnod;
    }
    else
    {
            /*Checks removed node is root*/
            if(_this->m_root == _oldnod)
            {
                _this->m_root = _newnod;
            }
            else
            {
                _oldnod->m_parnt->m_small = _newnod;
            }
    }
    /*replace the links of newnod with that that will replce it*/

    /* case if the _newnode from BIG SIDE*/
    if(_oldnod->m_big != 0 && _oldnod->m_big !=&_this->m_End)
    {
        ReplaceLinkOnBigSide(_this, _newnod, _oldnod);
    }
    else
    {
        /* case if the _newnode from small SIDE*/
        ReplaceLinkOnSmallSide(_this, _newnod, _oldnod);
    }
    _newnod->m_parnt = _oldnod->m_parnt;
    TreeInvalidateNode(_oldnod);
    free(_oldnod);
}

static void ReplaceLinkOnBigSide(Tree* _this,subtr* _newnod,subtr* _oldnod)
{
    /*if the _newnod is NOT the child of _oldnod*/
    if( _oldnod->m_big !=  _newnod)
    {
        _newnod->m_parnt->m_small = _newnod->m_big;
        if(_newnod->m_big)
        {
                _newnod->m_big->m_parnt = _newnod->m_parnt;
        }
        _newnod->m_big = _oldnod->m_big;
        _oldnod->m_big->m_parnt = _newnod;
    }
    _newnod->m_small = _oldnod->m_small;
    if(_oldnod->m_small && _oldnod->m_small !=&_this->m_End )
    {
        _oldnod->m_small->m_parnt =_newnod;
    }
    if(_oldnod->m_small == &_this->m_End)
    {
        _this->m_Begin = _newnod;
    }
    return;
}

static void ReplaceLinkOnSmallSide(Tree* _this,subtr* _newnod,subtr* _oldnod)
{
    /*if the _newnod is NOT the child of _oldnod*/
    if( _oldnod->m_small !=  _newnod)
    {
        _newnod->m_parnt->m_big = _newnod->m_small;
        if(_newnod->m_small)
        {
                _newnod->m_small->m_parnt = _newnod->m_parnt;
        }
        _newnod->m_small= _oldnod->m_small;
        _oldnod->m_small->m_parnt = _newnod;
    }
    _newnod->m_big = _oldnod->m_big;
    if(_oldnod->m_big)
    {
        _oldnod->m_big->m_parnt =_newnod;
    }
    return;
}

/*_node cann't be 0 this condition has to be checked in previous function that calls to this*/
static subtr* TreeFindMinOnLeaf(subtr* _node)
{
    assert(_node);

    if( _node->m_small)
    {
        _node=TreeFindMinOnLeaf( _node->m_small);
    }

    return  _node;
}

/*_node cann't be 0 this condition has to be checked in previous function that calls to this*/
static subtr* TreeFindMaxOnLeaf(subtr* _node)
{
    if( _node->m_big)
    {
        _node=TreeFindMaxOnLeaf( _node->m_big);
    }
    return  _node;
}

/*Seaches the node wich will replace the _iter node.
It is non the NEXT.Initially it searchs the minimal data on right side. If not found,
the maximal on left side, if no niether big niether small side , this  node has no childes
and function returns itself (_iter)*/
static TreeIter TreeFindNodeForReplace(Tree* _this, TreeIter _iter)
{
    subtr*          node=(subtr*)_iter;

    /*Search on big side and below*/
    if(node->m_big !=0 && node->m_big != &_this->m_End)
    {
        return (TreeIter)TreeFindMinOnLeaf(((subtr*)_iter)->m_big);
    }
     /*Search on small side and below, if node->m_small == 0 or node->m_small == &_this->m_End,
     this node has no childers and it was already check in funciton that called to it*/
    else
    {
         return (TreeIter)TreeFindMaxOnLeaf(((subtr*)_iter)->m_small);
    }
}

static void TreeUpdateEndBegin(Tree* _this,subtr* _newnode)
{
    /*Root initiallizing*/
    if( !_this->m_root->m_small && !_this->m_root->m_big)
    {
        _newnode->m_big = &(_this->m_End);
        _newnode->m_small = &(_this->m_End);
        _this->m_End.m_parnt=_newnode;
        _this-> m_Begin=_newnode;

        return;
    }

    /*Update the Begin*/
    if(_this->m_lessF(_newnode->m_data,_this->m_Begin->m_data))
    {
        _this-> m_Begin=_newnode;
        _newnode->m_small= &_this->m_End;
    }

     /*Update the End*/
    if(!_this->m_lessF(_newnode->m_data,_this->m_End.m_parnt->m_data))
    {
         _newnode->m_big = &(_this->m_End);
        _this->m_End.m_parnt=_newnode;
    }

    return;
}

static subtr* TreeFindSubtr(subtr* _End, subtr* _root, void* _data, Less _less)
{
    if ( _root == 0 || _root == _End)
    {
        return _End;
    }

     if ( _less( _root->m_data,_data ) )
    {
        return TreeFindSubtr(_End,_root->m_big,_data,_less);
    }

    if ( _less(_data,_root->m_data ) )
    {
        return TreeFindSubtr(_End,_root->m_small,_data,_less);
    }
     return _root;
}

static subtr* TreeInsertSubtr(subtr* _End, subtr* _root,subtr* _newnode,Less _less)
{
    if ( _root == 0 || _root == _End)
    {
        return _newnode;
    }

    _newnode->m_parnt = _root;

    /*Compare with small side, if m_data < than _newnode->data moves to big side*/
    if ( _less( _root->m_data, _newnode->m_data ))
    {
        _root->m_big =TreeInsertSubtr(_End,_root->m_big,_newnode,_less);
    }
    else
    {
        _root->m_small =TreeInsertSubtr(_End,_root->m_small,_newnode,_less);
    }
     return _root;
}


/*****************************************************************************************************************
**************************************************************************************************************/
#ifdef  unitest_bittree_local

#define STATUS(x)         !(x)?        "SUCCESS":"FAILUER"
#define LOGERR(x)         printf("Test function %30s  %10s\n",#x,STATUS(x));

typedef struct pair_t
{
    long        m_ID;
    int         m_weight;

}pair;


int IntLess( void* _data, void* _newdata)
{
    return (*(long*)_data) < (*(long*)_newdata);
}

pair* generatpair(int num)
{
    pair*   p=malloc(sizeof(pair));

    p->m_weight = rand()%100 + 50;
    p->m_ID = 1000 + 10*num;
    return p;
}
int TreePrintID(void* _data,void* _state)
{
    fprintf(stderr,"  %ld \n",*(long*)_data);
    fflush(stderr);
    return 0;
}

void regression_test();
int  unitest_TreeNew();
int  unitest_TreeInsert();
int  unitest_TreeFind();
int  unitest_TreeNext();
int  unitest_TreePrev();
int  unitest_TreeRemove();
int  unitest_TreeDelete();

int main()
{
    regression_test();
    return 0;
}

void regression_test()
{
    LOGERR(unitest_TreeNew());
    LOGERR(unitest_TreeInsert());
    LOGERR(unitest_TreeFind());
    LOGERR(unitest_TreeNext());
    LOGERR(unitest_TreePrev());
    LOGERR(unitest_TreeRemove());
    LOGERR(unitest_TreeDelete());
}

int unitest_TreeNew()
{
    Tree* tree=TreeNew(IntLess);

    if (tree)
    {
        return 0;
    }
    return 1;
}

int unitest_TreeInsert()
{
     Tree* tree=TreeNew(IntLess);
     int   count=0;

     int ID1 = 5;
     int ID2 = 8;
     int ID3 = 3;
     int ID4 = 4;
     int ID5 = 2;
     int ID6 = 7;
     int ID7 = 12;


     pair* p1=generatpair(ID1);
     pair* p2=generatpair(ID2);
     pair* p3=generatpair(ID3);
     pair* p4=generatpair(ID4);
     pair* p5=generatpair(ID5);
     pair* p6=generatpair(ID6);
     pair* p7=generatpair(ID7);

     TreeInsert(tree,p1);
     TreeInsert(tree,p2);
     TreeInsert(tree,p3);
     TreeInsert(tree,p4);
     TreeInsert(tree,p5);
     TreeInsert(tree,p6);
     TreeInsert(tree,p7);


    if(tree->m_End.m_parnt->m_data == p7)
    {
        ++count;
    }
    if(tree->m_Begin->m_data == p5)
    {
        ++count;
    }
    if(tree->m_root->m_big->m_small->m_parnt == tree->m_root->m_big->m_big->m_parnt)
    {
        ++count;
    }
    if(*(long*)(tree->m_root->m_big->m_small->m_parnt->m_data) == 1080)
    {
        ++count;
    }
    if(tree->m_root->m_small->m_small->m_parnt == tree->m_root->m_small->m_big->m_parnt)
    {
        ++count;
    }
    if(*(long*)(tree->m_root->m_small->m_small->m_parnt->m_data) == 1030)
    {
        ++count;
    }
    if(*(long*)tree->m_root->m_small->m_small->m_data == *(long*)tree->m_Begin->m_data && *(long*)tree->m_Begin->m_data == 1020 )
    {
        ++count;
    }

    if( count == 7)
    {
        return 0;
    }
    return 1;
}

int unitest_TreeFind()
{
     Tree* tree=TreeNew(IntLess);

     int ID1 = 5;
     int ID2 = 8;
     int ID3 = 3;
     int ID4 = 4;
     int ID5 = 2;
     int ID6 = 7;
     int ID7 = 10;
     int ID8 = 6;
     TreeIter   itr;

     pair* p1=generatpair(ID1);
     pair* p2=generatpair(ID2);
     pair* p3=generatpair(ID3);
     pair* p4=generatpair(ID4);
     pair* p5=generatpair(ID5);
     pair* p6=generatpair(ID6);
     pair* p7=generatpair(ID7);
     pair* p8=generatpair(ID8);

     TreeInsert(tree,p1);
     TreeInsert(tree,p2);
     TreeInsert(tree,p3);
     TreeInsert(tree,p4);
     TreeInsert(tree,p5);
     TreeInsert(tree,p6);
     TreeInsert(tree,p7);

    if((itr = TreeFind(tree,p5)))/*Fined  the minimal*/
    {
        if(((subtr*)itr)->m_data == p5)
        {
            if(&tree->m_End == (subtr*)(itr = TreeFind(tree,p8)))/*Not existed*/
            {
                if((itr = TreeFind(tree,p7)))
                {
                   if(((subtr*)itr)->m_data == p7)/*The maximal*/
                   {
                       if((itr = TreeFind(tree,p6)))/*some inside*/
                       {
                           if(((subtr*)itr)->m_data == p6)
                           {
                               return 0;
                           }
                       }
                   }
                }
            }
        }
    }
    return 1;
}

int  unitest_TreeNext()
{
    Tree* tree=TreeNew(IntLess);

     int ID1 = 5;
     int ID2 = 8;
     int ID3 = 3;
     int ID4 = 4;
     int ID5 = 2;
     int ID6 = 7;
     int ID7 = 10;
     TreeIter   itr;
     TreeIter   itr1;

     pair* p1=generatpair(ID1);
     pair* p2=generatpair(ID2);
     pair* p3=generatpair(ID3);
     pair* p4=generatpair(ID4);
     pair* p5=generatpair(ID5);
     pair* p6=generatpair(ID6);
     pair* p7=generatpair(ID7);

     TreeInsert(tree,p1);
     TreeInsert(tree,p2);
     TreeInsert(tree,p3);
     TreeInsert(tree,p4);
     TreeInsert(tree,p5);
     TreeInsert(tree,p6);
     TreeInsert(tree,p7);

     itr = TreeFind(tree,p5);
     if (TreeNext(itr) != TreeFind(tree,p3))
     {
         return 1;
     }

     itr = TreeFind(tree,p3);
     itr1 = TreeNext(itr);
     if (TreeNext(itr) != TreeFind(tree,p4))
     {
         return 1;
     }

     itr = TreeFind(tree,p4);
     itr1 = TreeNext(itr);
     if (TreeNext(itr) != TreeFind(tree,p1))
     {
         return 1;
     }

     itr = TreeFind(tree,p1);
     itr1 = TreeNext(itr);
     if (TreeNext(itr) != TreeFind(tree,p6))
     {
         return 1;
     }

    itr = TreeFind(tree,p6);
     itr1 = TreeNext(itr);
     if (TreeNext(itr) != TreeFind(tree,p2))
     {
         return 1;
     }

     itr = TreeFind(tree,p2);
     itr1 = TreeNext(itr);
     if (TreeNext(itr) != TreeFind(tree,p7))
     {
         return 1;
     }

     itr = TreeFind(tree,p7);
     itr1 = TreeNext(itr);
     if ((subtr*)TreeNext(itr) == &tree->m_End)
     {
         return 0;
     }

     return 1;
}

int  unitest_TreePrev()
{
    Tree* tree=TreeNew(IntLess);
     int count=0;
     int ID1 = 5;
     int ID2 = 8;
     int ID3 = 3;
     int ID4 = 4;
     int ID5 = 2;
     int ID6 = 7;
     int ID7 = 10;
     TreeIter   itr;
     TreeIter   itr1;

     pair* p1=generatpair(ID1);
     pair* p2=generatpair(ID2);
     pair* p3=generatpair(ID3);
     pair* p4=generatpair(ID4);
     pair* p5=generatpair(ID5);
     pair* p6=generatpair(ID6);
     pair* p7=generatpair(ID7);

     TreeInsert(tree,p1);
     TreeInsert(tree,p2);
     TreeInsert(tree,p3);
     TreeInsert(tree,p4);
     TreeInsert(tree,p5);
     TreeInsert(tree,p6);
     TreeInsert(tree,p7);


     itr = TreeFind(tree,p7);
     itr1 = TreePrev(itr);
     if ( TreePrev(itr) == TreeFind(tree,p2))
     {
         ++count;
     }

     itr = TreeFind(tree,p2);
     itr1 = TreePrev(itr);
     if (TreePrev(itr) == TreeFind(tree,p6))
     {
         ++count;
     }

     itr = TreeFind(tree,p6);
     itr1 = TreePrev(itr);
     if (TreePrev(itr) == TreeFind(tree,p1))
     {
          ++count;
     }

     itr = TreeFind(tree,p1);
     itr1 = TreePrev(itr);
     if (TreePrev(itr) == TreeFind(tree,p4))
     {
          ++count;
     }

     itr = TreeFind(tree,p4);
     itr1 = TreePrev(itr);
     if (TreePrev(itr) == TreeFind(tree,p3))
     {
         ++count;
     }

     itr = TreeFind(tree,p3);
     itr1 = TreePrev(itr);
     if (TreePrev(itr) == TreeFind(tree,p5))
     {
        ++count;
     }

     itr = TreeFind(tree,p5);
     itr1 = TreePrev(itr);
     if ((subtr*)TreePrev(itr) == &tree->m_End)
     {
         return 0;
     }
     return 1;
}

int  unitest_TreeRemove()
{
    Tree* tree=TreeNew(IntLess);
     int ID1 = 50;
     int ID2 = 80;
     int ID3 = 30;
     int ID4 = 40;
     int ID5 = 20;
     int ID6 = 70;
     int ID7 = 100;
     int ID8 = 75;
     int ID9 = 45;
     int ID10 = 35;
     int ID11 = 38;
     int ID12 = 32;
     int ID13 = 90;
     int ID14 = 98;
     int ID15 = 95;
     int ID16 = 25;
     int ID17 = 48;

     TreeIter   itr;
     TreeIter   itr1;

     TreeIter   EndItr;
     subtr*   n;
     subtr*   n1;
     subtr*   n2;
     subtr*   n3;

     pair* p1=generatpair(ID1);
     pair* p2=generatpair(ID2);
     pair* p3=generatpair(ID3);
     pair* p4=generatpair(ID4);
     pair* p5=generatpair(ID5);
     pair* p6=generatpair(ID6);
     pair* p7=generatpair(ID7);
     pair* p8=generatpair(ID8);
     pair* p9=generatpair(ID9);
     pair* p10=generatpair(ID10);
     pair* p11=generatpair(ID11);
     pair* p12=generatpair(ID12);
     pair* p13=generatpair(ID13);
     pair* p14=generatpair(ID14);
     pair* p15=generatpair(ID15);
     pair* p16=generatpair(ID16);
     pair* p17=generatpair(ID17);

    /*Test of cases only root , root+one side*/

    /*1.Nothing inserted*/

     if(!TreeIsEmpty(tree))
     {
         return 1;
     }

      /*Only root*/

     EndItr=TreeEnd(tree);
     TreeInsert(tree,p8);
     printf(" Tree with only root = 750 :\n ");
     TreeFor_Each(tree,TreePrintID,0);
     itr = TreeFind(tree,p8);
     printf(" After Remove 750 :\n ");
     itr=TreeRemoveNode(tree,itr);
     if(itr == EndItr);
     {
          printf(" Nothing to remove \n ");
          TreeFor_Each(tree,TreePrintID,0);

     }

     /*And root m_big node*/


     TreeInsert(tree,p6);
     TreeInsert(tree,p15);

     printf(" Initial Root = 700 , and big is 950 :\n ");
     TreeFor_Each(tree,TreePrintID,0);
     itr = TreeFind(tree,p6);
     printf(" After Remove 700 :\n ");
     itr=TreeRemoveNode(tree,itr);
     TreeFor_Each(tree,TreePrintID,0);
     printf(" After Remove 950 :\n ");
     itr=TreeRemoveNode(tree,itr);
     if(itr == EndItr);
     {
          printf(" Nothing to remove \n ");
          TreeFor_Each(tree,TreePrintID,0);
     }
     putchar('\n');


     /*And root m_small node*/


     TreeInsert(tree,p6);
     TreeInsert(tree,p5);

     printf(" Initial Root = 700 , and small is 200 :\n ");
     TreeFor_Each(tree,TreePrintID,0);
     itr = TreeFind(tree,p6);
     itr1 = TreeFind(tree,p5);
     n1 = (subtr*)itr;
     n2 = (subtr*)itr1;
     printf(" After Remove 700 :\n ");
     itr=TreeRemoveNode(tree,itr);
     TreeFor_Each(tree,TreePrintID,0);
     printf(" After Remove 200 :\n ");
     itr=TreeRemoveNode(tree,itr);
     if(itr == EndItr);
     {
          printf(" Nothing to remove \n ");
          TreeFor_Each(tree,TreePrintID,0);
     }
     putchar('\n');



     TreeInsert(tree,p1);
     TreeInsert(tree,p2);
     TreeInsert(tree,p3);
     TreeInsert(tree,p4);
     TreeInsert(tree,p5);
     TreeInsert(tree,p6);
     TreeInsert(tree,p7);
     TreeInsert(tree,p9);
     TreeInsert(tree,p10);
     TreeInsert(tree,p11);
     TreeInsert(tree,p12);
     TreeInsert(tree,p13);
     TreeInsert(tree,p14);
     TreeInsert(tree,p15);
     TreeInsert(tree,p16);
     TreeInsert(tree,p17);

    TreeFor_Each(tree,TreePrintID,0);
    putchar('\n');
    printf(" Removes 200 :\n ");/*Removes Begin with 1 m_big*/
    itr = TreeFind(tree,p5);
    itr=TreeRemoveNode(tree,itr);
    TreeFor_Each(tree,TreePrintID,0);
    putchar('\n');

    printf(" Removes 250 :\n ");/*Removes Begin without m_big*/
    itr = TreeFind(tree,p16);
    itr=TreeRemoveNode(tree,itr);
    TreeFor_Each(tree,TreePrintID,0);
    putchar('\n');

    printf(" Removes 300 :\n ");/*Removes Begin with m_big with long least*/
    itr=TreeRemoveNode(tree,itr);
    TreeFor_Each(tree,TreePrintID,0);
    putchar('\n');

    printf(" Removes 400 :\n ");/*Removes middle with both children*/
    itr = TreeFind(tree,p4);
    itr=TreeRemoveNode(tree,itr);
    TreeFor_Each(tree,TreePrintID,0);
    putchar('\n');

    printf(" Removes 500 :\n ");/*Removes root with both children, his next is not his child*/
    itr = TreeFind(tree,p1);
    itr=TreeRemoveNode(tree,itr);
    TreeFor_Each(tree,TreePrintID,0);
    putchar('\n');

    printf(" Removes 800 :\n ");/*Removes at right side of root*/
    itr = TreeFind(tree,p2);
    itr=TreeRemoveNode(tree,itr);
    TreeFor_Each(tree,TreePrintID,0);
    putchar('\n');

    n =(subtr*)  TreeFind(tree,p7);/*100*/
    n1 =(subtr*)  TreeFind(tree,p13);/*90*/
    n2 =(subtr*) TreeFind(tree,p14);/*98*/
    n3 =(subtr*) TreeFind(tree,p15);/*95*/

    printf(" Removes 900 :\n ");/*Removes above End and takes "Next" from below of Last Valid*/
    itr=TreeRemoveNode(tree,itr);
    TreeFor_Each(tree,TreePrintID,0);
    putchar('\n');

    itr =TreeFind(tree,p7);
    printf(" Removes 2000 :\n ");/*Removes  Last Valid*/
    itr=TreeRemoveNode(tree,itr);
    TreeFor_Each(tree,TreePrintID,0);
    putchar('\n');

     return 0;
}

int  unitest_TreeDelete()
{
    Tree* tree=TreeNew(IntLess);
     int ID1 = 50;
     int ID2 = 80;
     int ID3 = 30;
     int ID4 = 40;
     int ID5 = 20;
     int ID6 = 70;
     int ID7 = 100;
     int ID8 = 75;

     pair* p1=generatpair(ID1);
     pair* p2=generatpair(ID2);
     pair* p3=generatpair(ID3);
     pair* p4=generatpair(ID4);
     pair* p5=generatpair(ID5);
     pair* p6=generatpair(ID6);
     pair* p7=generatpair(ID7);
     pair* p8=generatpair(ID8);

     TreeInsert(tree,p1);
     TreeInsert(tree,p2);
     TreeInsert(tree,p3);
     TreeInsert(tree,p4);
     TreeInsert(tree,p5);
     TreeInsert(tree,p6);
     TreeInsert(tree,p7);
     TreeInsert(tree,p8);
     TreeDeleteTree(tree);
     return 0;
}

#endif /* unitest_bittree_local*/


#ifdef utestTree
#define IS_SUCCESS(err,str) if (err) {printf("\n success with ...%s test \n",str);}\
else{printf("\n fail with...%s  test",str);}
#define Fail_pattern(err,str) if (err) {printf("\n fail pattern is ...%s \n ",str); return 0;}
#include<string.h>
#include<math.h>
#include<time.h>

void  Regresion_test(void);
void  AddInOrder(subtr* _root,int* _arr,int *_index);
int   TreeNewInsertTest();
int   ChekSortArr(int *_arr,int _elements);
int*  MakeRandomArr(int _digits);
void  RandArray(int  *_arr,int _elements);
int   TreeIterChek(void);
int   TreeRemoveTest(void);
int   IsLess(void* _dataA,void* _dataB);
void  PrintInOrder(subtr* _root);

int main()
{

   Regresion_test();

   return 0;
}


int    TreeNewInsertTest()
{
    Tree* tree=TreeNew(IsLess);
    int arr[10];
    int i=0;
    TreeIter it;

    int *array=MakeRandomArr(1);/*2 digits mean 100 elemnts*/

    for (i=0;i<10;i++)
    {
       it=TreeInsert(tree,(void*)*(array+i));
       Fail_pattern((int)TreeGetData(it)!=*(array+i),"taking iter value");
    }

    i=0;






    for(i=1;i<=9;i++)
    {
        Fail_pattern( (int)TreeGetData(TreeFind(tree, (void*)(i) ) )!=*(array+i),"tree find");
    }



    TreeDeleteTree(tree);

    return 1;
}

int TreeIterChek(void)
{
    Tree* tree=TreeNew(IsLess);
    int i=0;
    TreeIter it;

    int *array=MakeRandomArr(3);/*2 digits mean 100 elemnts*/

    for (i=0;i<1000;i++)
    {
       it=TreeInsert(tree,(void*)*(array+i));
/*       printf("--%d--",*(array+i));*/

       Fail_pattern((int)TreeGetData(it)!=*(array+i),"taking iter value");
    }

    it=TreeBegin(tree);

    for(i=1;i<1000;i++)
    {
        Fail_pattern((int)TreeGetData(it)!=i,"TreeNext operation");
        it=TreeNext(it);
    }


    for(i=1000;i>1;i--)
    {
        Fail_pattern((int)TreeGetData(it)!=i,"TreePrev operation");
        it=TreePrev(it);
    }




    return 1;

}

int  TreeRemoveTest(void)
{
    Tree* tree=TreeNew(IsLess);
    int i=0;
    TreeIter it;

    int *array=MakeRandomArr(3);/*2 digits mean 100 elemnts*/

    for (i=0;i<1000;i++)
    {
        it=TreeInsert(tree,(void*)*(array+i));
    }

    it=TreeBegin(tree);

    while (it!=TreeEnd(tree))
    {

        it=TreeRemoveNode(tree,it);
/*         printf("\n");
 *         PrintInOrder(tree->root);
 */
    }

    Fail_pattern(!TreeIsEmpty(tree),"did not remove all nodes");

    return 1;
}

void    Regresion_test(void)
{
/*     IS_SUCCESS(TreeNewInsertTest(),    "TreeNew TreeInsert TreeGetData TreeFind");
 *     IS_SUCCESS(TreeIterChek(),  "TreeNext TreePrev TreeBegin TreeEnd ");
 */
    IS_SUCCESS(TreeRemoveTest(),  "TreeRemove TreeIsEmpty  ");
}


int        IsLess(void* _dataA,void* _dataB)
{
    if ((int)_dataA >= (int)_dataB)
    {
        return 0;
    }

    return 1;
}

void   AddInOrder(subtr* _root,int* _arr,int *_index)
{
   if (_root)
   {
       AddInOrder(_root->m_small,_arr,_index);
/*       printf("%d \n",(int)_root->data);*/
       *(_arr+*_index)=(int)_root->m_data;
       ++(*_index);
       AddInOrder(_root->m_big,_arr,_index);
   }
}

void  PrintInOrder(subtr* _root)
{

   if (_root)
   {
       PrintInOrder(_root->m_small);
       printf("--%d--",(int)_root->m_data);
       PrintInOrder(_root->m_big);
   }
}

int*  MakeRandomArr(int _digits)
{

    int     elements,*arr;

    elements=pow(10,_digits);
    arr=malloc(sizeof(int)*elements);

    RandArray(arr,elements);

    return arr;
}

int  ChekSortArr(int *_arr,int _elements)
{
    int      i=1;

    for(;i<_elements;i++)
    {
        if(_arr[i]<_arr[i-1])
        {
            return 0;
        }
    }

    return 1;
}

void         RandArray(int  *_arr,int _elements)
{
     int        *arr=_arr,value2,value1,i,temp;

     srand(time(NULL));

     for(i=1;i<_elements+1;i++,arr++)
     {
         *arr=i;
     }

     for(i=0;i<_elements;i++)
     {
         value1=rand()%_elements;
         value2=rand()%_elements;
         if (value1!=value2)
         {
             temp=*(_arr+value1);
             *(_arr+value1)=*(_arr+value2);
             *(_arr+value2)=temp;
         }
     }
}

#endif/*utestTree*/

